/*
 * @lc app=leetcode.cn id=34 lang=javascript
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start

var findFirstPosition = function (nums, target) {
  let start = 0, end = nums.length - 1;
  let mid;
  while (start < end) {
    mid = start + (end - start) / 2 >> 0;
    if (nums[mid] === target) {
      end = mid;
    } else if (nums[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return nums[start] === target ? start : -1;
}

var findLastPosition = function (nums, target) {
  let start = 0, end = nums.length - 1;
  let mid;
  while (start < end) {
    mid = Math.ceil((start + end) / 2);
    if (nums[mid] === target) {
      start = mid;
    } else if (nums[mid] > target) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return nums[end] === target ? end : -1;
}
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  if (nums.length === 0) {
    return [-1, -1];
  }
  if (nums.length === 1) {
    return nums[0] === target ? [0, 0] : [-1, -1];
  }
  let firstPosition = findFirstPosition(nums, target);
  if (firstPosition === -1) {
    return [-1, -1];
  }
  let lastPosition = findLastPosition(nums, target);
  return [firstPosition, lastPosition];
};
// @lc code=end
